package structure.mySort;

import java.util.Arrays;
import java.util.Stack;

public class MySort {

    /**
     * 时间复杂度:O(N^2)
     *      最好的情况是O(N):对于直接插入排序来说,最好的情况就是数据有序的时候.
     *      根据这个结论,推导出另一个结论:对于直接插入排序来说,数据越有序,越快.
     *
     * 空间复杂度:O(1)
     * 稳定性:稳定的 (本身是稳定的,如果在 array[j] > tmp 处加等号就会变成不稳定的了.)
     *
     *一个稳定的排序,是可以实现为不稳定的排序.
     *但是一个本身就不稳定的排序,是不可以变成稳定的排序的.
     *
     * 插入排序 (经常使用在 数据量不多 且 整体数据 趋于有序)
     * @param array 待排序序列
     */
    public static void insertSort(int[] array){
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];
            int j = i-1;
            for (; j >= 0; j--) {
                if (array[j] > tmp){
                    array[j+1] = array[j];
                }else {
                    //array[j+1] = tmp; 只要j回退了的时候,遇到了比tmp小的元素就结束这次的比较
                    break;
                }
            }
            //j回退到了 小于0 的地方
            array[j+1] = tmp;
        }
    }

    /**
     * 分组排序
     * @param array 待排序序列
     * @param gap   组数
     */
    public static void shell(int[] array,int gap){
        for (int i = gap; i < array.length; i++) {
            int j = i-gap;
            int tmp = array[i];
            for (; j >= 0; j-=gap) {
                if (array[j] > tmp){
                    array[j+gap] = array[j];
                }else{
                    break;
                }

            }
            array[j+gap] = tmp;
        }
    }

    /**
     * 希尔排序
     * 时间复杂度:O(n^1.3 - n^1.5)
     * 稳定性:不稳定的
     *      看在比较的过程中 是否发生了跳跃式的交换 如果发生了跳跃式的交换 那么就是不稳定的排序
     * @param array 待排序序列
     */
    public static void shellSort(int[] array){
        int gap = array.length;
        while(gap > 1){
            shell(array,gap);
            gap /= 2;
        }
        shell(array,1); //保证最后是1组
    }

    /**
     * 选择排序
     * 时间复杂度:O(n^2)
     * 空间复杂度:O(1)
     * 稳定性:不稳定的
     * @param array 待排序序列
     */
    public static void selectSort(int[] array){

        for (int i = 0; i < array.length-1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < array[minIndex]){
                    minIndex = j;
                }
            }
            if (array[i] > array[minIndex]){
                int tmp = array[i];
                array[i] = array[minIndex];
                array[minIndex] = tmp;
            }
        }
    }

    /**
     * 时间复杂度:O(N * log N)
     * 空间复杂度:O(1)
     * 稳定性:不稳定
     * 根排序(使用大根堆 排升序)
     * @param array 待排序数组
     */
    public static void heapSort(int[] array){
        //建堆 O(N)
        createHeap(array);
        int end = array.length-1;
        //交换然后调整 O(N*logN) [交换n次,但每次需要向下调整,向下调整最多调整树高即logN)
        while (end > 0){
            int tmp = array[0];
            array[0] = array[end];
            array[end] = tmp;
            shiftDown(array,0,end);
            end--;
        }
    }

    /**
     * 创建大根堆
     * @param array 待排序数组
     */
    public static void createHeap(int[] array){
        for (int parent = (array.length-1-1)/2; parent >=0 ; parent--) {
            shiftDown(array,parent,array.length);
        }
    }

    /**
     * 向下调整
     * @param parent 父亲节点
     * @param len 数组长度(对应下标值为空)
     */
    public static void shiftDown(int[] array,int parent,int len){
        int child = 2*parent+1;
        while(child < len){
            if (child+1 < len && array[child] < array[child+1]){
                child++;
            }
            if (array[parent] < array[child]){
                int tmp = array[parent];
                array[parent] = array[child];
                array[child] = tmp;
                parent = child;
                child = parent*2+1;
            }else {
                break;
            }
        }
    }

    /**
     * 冒泡排序
     * 时间复杂度:O(N^2)
     *  有序情况下:O(N)
     * 空间复杂度:O(1)
     * 稳定性:稳定的
     * @param array 待排序数组
     */
    public static void bubbleSort(int[] array){
        for (int i = 0; i < array.length-1; i++) {
            boolean flg = false;
            for (int j = 0; j < array.length-1-i; j++) {
                if (array[j] > array[j+1]){
                    int tmp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = tmp;
                    flg = true;
                }
            }
            if (flg == false) break;
        }
    }

    /**
     * 时间复杂度: [当成一棵二叉树,每层都进行找基准点,找基准点为n,有logn层.]
     *      最好:[每次可以均匀的分割待排序序列] O(n*logn)
     *      最坏:数据有序 或者 逆序的情况 O(n^2)
     * 空间复杂度:
     *      最好:O(logn)
     *      最坏:O(n)  单分支的一棵树
     * 稳定性:不稳定的
     * @param array 待排序数组
     */
    public static void quickSort1(int[] array){
        quick(array,0,array.length-1);
    }

    public static void quick(int[] array,int left,int right){
        if (left >= right) return;

        //找基准之前,找到中间大小的值.--使用三数取中法.
        int midValIndex = findMidValIndex(array,left,right);
        //让中间值的与start的值交换,确保拿到的值处于中间位置.
        int tmp = array[midValIndex];
        array[midValIndex] = array[left];
        array[left] = tmp;

        int pivot = partition(array,left,right);
        quick(array,left,pivot-1);
        quick(array,pivot+1,right);
    }

    public static int findMidValIndex(int[] array,int start,int end){
        int mid = (start + end)/2;
        if (array[start] < array[end]) {
            if (array[mid] < array[start]){
                return start;
            }else if (array[mid] > array[end]){
                return end;
            }else {
                return mid;
            }
        }else{
            if (array[mid] > array[start]){
                return start;
            }else if (array[mid] < array[end]){
                return end;
            }else{
                return mid;
            }
        }
    }

    /**
     * 找基准点
     * @param array 代排序数组
     * @param start 起始点
     * @param end 末位点
     * @return 基准点
     */
    public static int partition(int[] array,int start,int end){
        int tmp = array[start];
        while (start < end){
            while (start < end && array[end] >= tmp){
                end--;
            }
            array[start] = array[end];
            while (start < end && array[start] <= tmp){
                start++;
            }
            array[end] = array[start];
        }
        array[start] = tmp;
        return start;
    }

    /**
     * 快速排序非递归实现方法(使用栈)
     * @param array 待排序数组
     */
    public static void quickSort(int[] array){
        int left = 0;
        int right = array.length-1;
        int pivot = partition(array,left,right);
        Stack<Integer> stack = new Stack<>();
        if (pivot > left + 1){
            //左边有两个元素
            stack.push(left);
            stack.push(pivot-1);
        }
        if (pivot < right -1){
            stack.push(pivot+1);
            stack.push(right);
        }

        while (!stack.isEmpty()){
            right = stack.pop();
            left = stack.pop();
            pivot = partition(array,left,right);
            if (pivot > left + 1){
                //左边有两个元素
                stack.push(left);
                stack.push(pivot-1);
            }
            if (pivot < right -1){
                stack.push(pivot+1);
                stack.push(right);
            }
        }

    }

    /**
     * 合并两个有序数组
     * @param array1 有序的数组1
     * @param array2 有序的数组2
     * @return 合并后的数组
     */
    public static int[] mergeArray(int[] array1,int[] array2){
        int s1 = 0;
        int e1 = array1.length-1;
        int s2 = 0;
        int e2 = array2.length-1;
        int[] tmp = new int[array1.length+array2.length];
        int i = 0;
            while (s1 <= e1 && s2 <= e2){
                if (array1[s1] > array2[s2]){
                    tmp[i] = array2[s2];
                    s2++;
                    i++;
                    //可以简写成tmp[i++] = array2[s2++];
                }else{
                    tmp[i] = array1[s1];
                    s1++;
                    i++;
                }
            }

        while (s1 <= e1){
            tmp[i] = array1[s1];
            i++;
            s1++;
        }
        while(s2 <= e2){
            tmp[i] = array2[s2];
            i++;
            s2++;
        }
        return tmp;
    }

    /**
     * 归并排序:
     * 时间复杂度:O(N*logN)  因为每层的元素的区间都是n,而logn表示有几层(高度).
     * 空间复杂度:O(N)  最坏情况下,合并申请的数组要与n一样大小,则为O(N).
     * 稳定性:稳定的排序
     * 如果 array[s1] <= array[s2] 不取等号 那么就是不稳定的排序
     * (如果s1小于等于则将s1放入,说明相对排序位置不会发生变化)
     *
     * 学过的排序 只有3个是稳定的:
     * 冒泡 插入 归并
     * @param array 待排序数组
     */
    public static void mergeSort1(int[] array){
        mergeSortInternal(array,0,array.length-1);
    }

    private static void mergeSortInternal(int[] array,int low,int high){
        if (low >= high) return;
        int mid = low + ((high - low) >>> 1); // (low + high)/2
        mergeSortInternal(array,low,mid);
        mergeSortInternal(array,mid+1,high);
        merge(array,low,mid,high);
    }

    private static void merge(int[] array,int low,int mid,int high){
        int s1 = low;
        int e1 = mid;
        int s2 = mid + 1;
        int e2 = high;
        int k = 0;
        int[] tmp = new int[high-low+1];

        while (s1 <= e1 && s2 <= e2){
            if (array[s1] <= array[s2]){
                tmp[k++] = array[s1++];
            }else{
                tmp[k++] = array[s2++];
            }
        }
        while (s1 <= e1){
            tmp[k++] = array[s1++];
        }
        while (s2 <= e2){
            tmp[k++] = array[s2++];
        }
        //拷贝tmp数组的元素 放入原来的数组array中
        for (int i = 0; i < k; i++) {
            array[i+low] = tmp[i];
        }
    }

    /**
     * 非递归实现归并排序
     * @param array 待排序数组
     */
    public static void mergeSort(int[] array){
        int nums = 1; //gap代表组内元素的个数
        while (nums < array.length){
            //每组每次都要进行遍历,确定要归并的区间.
            for (int i = 0; i < array.length; i+=nums*2) {
                int left = i;
                int mid = left + nums -1;
                //防止越界
                if (mid >= array.length){
                    mid = array.length-1;
                }
                int right = mid + nums;
                //防止越界
                if (right >= array.length){
                    right = array.length-1;
                }
                merge(array,left,mid,right);
            }
            nums *= 2;
        }
    }



    public static void main(String[] args) {
        int[] array = {5,12,9,23,4,10,1};
        //insertSort(array);
        //shellSort(array);
        //selectSort(array);
        //heapSort(array);
        //bubbleSort(array);
        //quickSort(array);
        mergeSort(array);
        //-----------
//        int[] array1 = {2,4,6,8,10};
//        int[] array2 = {1,3,5,7,9};
//        int[] array = mergeArray(array1,array2);
        System.out.println(Arrays.toString(array));
    }
}
